package com.example.nirvana.dataStructure.algorithm;

import com.example.nirvana.dataStructure.LineNode;

/**
 * 递归反转链表
 */
public class LineReverse {
    LineNode successor = null; //后驱节点
    /**
     * 反转整个链表
     *
     * @param head 头节点
     * @return 新的头节点
     */
    LineNode reverse(LineNode head) {
        if (head.getNext() == null) return head;
        LineNode last = reverse(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return last;
    }

    /**
     * 反转链表前N个节点
     *
     * @param head 头节点
     * @param n 节点数（n < 链表长度）
     * @return 新的头节点
     */
    LineNode reverseN(LineNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.getNext();
            return head;
        }
        LineNode last = reverseN(head.getNext(), n - 1);
        head.getNext().setNext(head);
        head.setNext(successor);
        return last;
    }

    /**
     * 反转链表的一部分
     *
     * @param head 头节点
     * @param m 反转起点
     * @param n 反转终点
     * @return 新的头节点
     */
    LineNode reverseBetween(LineNode head, int m, int n) {
        if (m == 1) {
            return reverseN(head, n);
        }
        head.setNext(reverseBetween(head.getNext(), m-1, n-1));
        return head;
    }

    /**
     * 反转区间 [a, b) 的元素，注意是左闭右开
     *
     * @param a 头节点
     * @param b 尾节点
     * @return 新的头节点
     */
    LineNode reverse(LineNode a, LineNode b) {
        LineNode pre = null, cur = a, next = a;
        while(cur != b) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * k 个一组反转链表
     *
     * @param head 头节点
     * @param k 组个数
     * @return 新的头节点
     */
    LineNode reverseKGroup(LineNode head, int k) {
        LineNode a = head, b = head;
        for (int i = 0; i < k; i++) {
            b = b.next;
        }
        LineNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);
        return newHead;
    }
}
